// 20. Valid Parentheses

// Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

// The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

package main

const left = '0'

var brackets = map[byte]byte{
	'(': left,
	'{': left,
	'[': left,
	')': '(',
	'}': '{',
	']': '[',
}

func isValid(s string) bool {
	l := len(s)
	if l == 0 {
		return true
	}

	stack := make([]byte, 0, l/4)
	for i := 0; i < l; i++ {
		c, ok := brackets[s[i]]
		if !ok {
			continue
		}

		if c == left {
			stack = append(stack, s[i])
			continue
		}

		if len(stack) == 0 || stack[len(stack)-1] != c {
			return false
		}
		stack = stack[:len(stack)-1]
	}

	return len(stack) == 0
}

func main() {
	str := "["
	println(isValid(str))
}
